package TestSort;

import java.util.Random;

public class InsertSort {
    public static int[] arr = new int[10_0000];

    public long testInsertSort() {
        InsertSort in = new InsertSort();
        in.initiateNotOrderArray();
        long inTime = System.currentTimeMillis();
        in.insertSort(this.arr);
        long outTime = System.currentTimeMillis();
        return outTime - inTime;
    }

    public void initiateNotOrderArray() {
        int i = 0;
        Random random = new Random();
        while (i < this.arr.length) {
            arr[i] = random.nextInt(10_0000);
            i++;
        }
    }

    public void initiateOrderArray () {
        int i = 0;
        while (i < this.arr.length) {
            arr[i] = i;
            i++;
        }
    }

    public int[] insertSort (int[] arr) {
        int j = 0;
        //i在j前面
        int i = j + 1;
        int tmp = i;
        //用i遍历数组
        while (i < arr.length) {
            while (j >= 0) {
                //找到比j下标小的值交换
                if (arr[tmp] < arr[j]) {
                    swap(tmp, j, arr);
                } else {
                    break;
                }
                tmp--;
                j--;
            }
            i++;
            tmp = i;
            j = i - 1;
        }
        return arr;
    }

    public static void swap (int a, int b, int[] arr) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] =tmp;
    }

    public static void main(String[] args) {
        InsertSort insert = new InsertSort();
        System.out.println(insert.testInsertSort());
    }
}
